package leo.mystudy.leetcode;

/**
 * Z字形变换
 *
 * @author chao.li@quvideo.com
 * @date 2018/6/29 11:08
 */
public class ZigZagConversion {
    //    将字符串 "PAYPALISHIRING" 以Z字形排列成给定的行数：
//
//    P   A   H   N
//    A P L S I I G
//    Y   I   R
//    之后从左往右，逐行读取字符："PAHNAPLSIIGYIR"
//
//    实现一个将字符串进行指定行数变换的函数:
//
//    string convert(string s, int numRows);
//    示例 1:
//
//    输入: s = "PAYPALISHIRING", numRows = 3
//    输出: "PAHNAPLSIIGYIR"
//    示例 2:
//
//    输入: s = "PAYPALISHIRING", numRows = 4
//    输出: "PINALSIGYAHRPI"
//    解释:
//
//    P     I    N
//    A   L S  I G
//    Y A   H R
//    P     I
    public static void main(String[] args) {
        ZigZagConversion zigZagConversion = new ZigZagConversion();
        //String s = "PAYPALISHIRING";
        String s = "a";
        System.out.println(zigZagConversion.convert(s, 1));
    }

    public String convert(String s, int numRows) {
        if (numRows <= 1) {
            return s;
        }
        int numColumns = getColumnNum(s, numRows);
        char[][] array = new char[numRows][numColumns];
        int row = 0;
        int col = 0;
        int groupSize = numRows * 2 - 2;// 一组的数量
        // 按z型规则向数组填值
        for (int i = 0; i < s.length(); i++) {
            array[row][col] = s.charAt(i);
            if (i % groupSize < numRows - 1) {
                row++;
            } else {
                row--;
                col++;
            }
        }
        // 输出
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j < numColumns; j++) {
                if (array[i][j] != (char) 0) {
                    sb.append(array[i][j]);
                }
            }
        }
        return sb.toString();
    }

    /**
     * 得到列数
     *
     * @param s
     * @param numRows
     * @return
     */
    private int getColumnNum(String s, int numRows) {
        if (numRows == 1) {
            return s.length();
        }
        // 以z的一个转折到底为一组，例如PAYPALISHIRING numRows为4时PAYPAL为一组
        int groupSize = numRows * 2 - 2;// 一组的数量
        int groupColumnNum = numRows - 1; // 一组的列数
        int groupCount = s.length() / groupSize; // 计算组数
        int result = groupCount * groupColumnNum;
        // 再根据余数得到总列数
        int remainder = s.length() % groupSize;
        if (remainder == 0) {
            return result;
        }
        if (remainder <= numRows) {
            return result + 1;
        }
        return result + remainder - numRows + 1;
    }

}
